package com.xyhuo.leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Allocator {

    int[] list;

    Map<Integer, List<int[]>> map = new HashMap<>();

    public Allocator(int n) {
        list = new int[n];
    }

    public int allocate(int size, int mID) {
        int index = 0;

        int tmp = 0;
        int emptyCount = 0;
        while (true) {
            if (list[index++] == 0) {
                emptyCount++;
            } else {
                emptyCount = 0;
                tmp = index;
            }

            if (emptyCount >= size) {
                break;
            }
            if (index == list.length) {
                return -1;
            }
        }

        for (int i = 0; i < size; i++) {
            list[tmp + i] = mID;
        }
        int[] it = {tmp, size};
        if (map.containsKey(mID)) {
            map.get(mID).add(it);
        } else {
            List<int[]> its = new ArrayList<>();
            its.add(it);
            map.put(mID, its);
        }
        return tmp;
    }

    public int freeMemory(int mID) {
        if (map.containsKey(mID)) {
            List<int[]> lists = map.get(mID);
            int result = 0;
            for (int[] it : lists) {
                int index = it[0];
                result += it[1];
                for (int i = 0; i < it[1]; i++) {
                    list[index + i] = 0;
                }
            }
            map.remove(mID);
            return result;
        } else {
            return 0;
        }
    }

    public static void main(String[] args) {
//        Allocator a = new Allocator(10);
//        int allocate = a.allocate(1, 1);
//        int allocate1 = a.allocate(1, 2);
//        int allocate2 = a.allocate(1, 3);
//        int i = a.freeMemory(2);
//        int allocate3 = a.allocate(1, 1);
//        int allocate4 = a.allocate(1, 1);
//        int i1 = a.freeMemory(1);
//        int allocate5 = a.allocate(10, 2);
//        int i2 = a.freeMemory(7);


        Allocator a = new Allocator(5);
        int i = a.freeMemory(4);
        int allocate = a.allocate(9, 5);
        int allocate1 = a.allocate(5, 8);
        int allocate2 = a.allocate(4, 8);
        int allocate3 = a.allocate(3, 2);
        int i1 = a.freeMemory(6);
        int allocate4 = a.allocate(9, 9);
        int i2 = a.freeMemory(6);
//
//
//        Allocator a = new Allocator(50);
//
//        int allocate = a.allocate(12, 6);
//        int allocate1 = a.allocate(28, 16);
//        int allocate2 = a.allocate(17, 23);
//        int allocate3 = a.allocate(50, 23);
//        int i1 = a.freeMemory(6);
//        int i2 = a.freeMemory(10);
//        int i3 = a.freeMemory(10);
//        int allocate4 = a.allocate(16, 8);
//        int allocate5 = a.allocate(17, 41);
//        int allocate6 = a.allocate(44, 27);
//        int allocate7 = a.allocate(12, 45);
//        int i4 = a.freeMemory(33);
//        int i5 = a.freeMemory(8);
//        int i6 = a.freeMemory(16);
//        int i7 = a.freeMemory(23);
//        int i8 = a.freeMemory(23);
//        int i9 = a.freeMemory(23);
//        int i10 = a.freeMemory(29);

    }
}
